package dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * 最长上升子序列(Longest Increasing Subsequence)
 */
public class LIS {
    public static int lengthOfLIS(int[] nums) {
        //dp数组存储原序列当前位置的升序排序
        ArrayList<Integer> dp = new ArrayList<>(nums.length);
        int len = 0;
        for (int num : nums) {
            List<Integer> subDp = dp.subList(0, len);
            int i = Collections.binarySearch(subDp, num);
            if (i < 0) {
                i = -(i + 1);
            }
            dp.add(i, num);
            if (i == len) {
                len++;
            }
        }
        return len;
    }
    
    public static void main(String[] args) {
//        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int[] nums = {3,1,2,6,4,5,3,3,3,3};
        int length = lengthOfLIS(nums);
        System.out.println("最长上升子序列的长度为：" + length);
    }
}
